NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/6741

Text File | 1996-08-05 | 2.6 KB | 54 lines

Path: sun001.spd.dsccc.com!spd!jmccarty
From: [e-mail] (Mike McCarty)
Newsgroups: comp.lang.c
Subject: Re: Finding a prime number
Date: 14 Feb 1996 19:50:53 GMT
Organization: DSC Communications Corporation, Plano, Texas USA
Message-ID: <4fteet$[e-mail]>
References: <[e-mail]> <4fp2kt$[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: aplo139.spd.dsccc.com

In article <[e-mail]>, Dik T. Winter <[e-mail]> wrote:
)In article <[e-mail]> [e-mail] (Kazimir Kylheku) writes:
) > Public key encryption requires large prime numbers. The current algorithms for

Public key encryption does -not- require large primes. What it requires
is a "trap door" function. Other means for developing trap door
functions than the RSA algorithm exist.

) > finding large prime numbers involve the generation of *random* large numbers
) > (like 100 digits, say) which are subject to *probabilistic* tests for
) > primeness. The argument is that if the random number can pass all these tests,
) > chances are very very small that it is not prime: chances as small as 1 in
) > 10^60 or something like that.
) >
) > If you found a deterministic way to efficiently find large primes, you'd win
) > some fame in the number theory world.
)
)There is no reason at all to use probable primes.  Primality proving is not
)so very time consuming.  For instance to *prove* that
) 1000000000000000000000000000000000000000000000000000000000000000000000\
) 000000000000000000000000000289
)is prime takes 14 seconds on a 100 MHz SGI R4k Indigo.  And that is about
)the expected time for 100-digit numbers.  BTW, this is the smallest prime
)100-digit number.  It took me just now much less than one minute to find it.
)Note that you need the time consuming part only for those numbers that pass
)the probabilistic tests.
)--
)dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, [phone]
)home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/


Indeed, primality proving is not too difficult. Just as large prime
computation is not difficult. I computed the largest prime known to man
on a 10 MHz XT computer in 1992. It took a little over 10 days. Using
the machines I have today, I can rerun it in about 4 hours. Really a
pretty trivial thing to do. But to -find- the largest known prime, that
is a real job. Just finding a large prime is not a big chore.

Mike
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

I don't speak for DSC.         <- They make me say that.